1. Field of the Invention
The present invention relates to navigation devices and programs, in which the volume of map data in a hierarchical structure is reduced and route search time is shortened as well as route quality is maintained.
2. Description of the Related Art
In navigation devices, for route search, various costs are set to each link and each between links (each node) according to road types such as a motorway, a toll road, a national road, a principle regional road, a prefectural road, and a narrow road, no right-turn and no left-turn, whether or not a traffic regulation such as a one-way traffic exists, a link length, a road width, the number of lanes, and the like. In search for an appropriate route from a current position to a destination, a route is searched from a departure point and from the destination along the links stored in map data. In an overlapped part between the search from the departure point and the search from the destination, the accumulated cost from the departure point and the accumulated cost from the destination are added, and a route with the smallest cost-added value is set as a most appropriate guidance route.
A hierarchized search technique using the map data in the hierarchical structure is known as a method for shortening a time required for such route search (refer to Japanese Patent Application; Publication No. JP-A-2-56591). The map data in the hierarchical structure includes detailed map data having all road data in a lower hierarchy level and broad area map data having only principle road data in a higher hierarchy level. The hierarchized search technique is a method of calculating the costs using the detailed map data for the vicinity of the departure point and the destination and roughly calculating the costs using less-detailed map data for a middle area of the route, and aggregating both results and outputting the aggregated result as the guidance route. According to such hierarchized search technique, if the distance between the departure point and the destination is long, an intermediate route can be searched using the less-detailed map data. Therefore, comparing to when performing the search for a whole route using the detailed map data, total time required for the route search can be shortened.
In addition, there is a technique of acquiring the most appropriate route in a shorter time, by terminating the route search when a shortest cost route has been determined in the map data in the lower hierarchy level where the route search was performed, without performing the route search in the map data in the higher hierarchy level which will be target for the route search (refer to Japanese Patent Application; Publication No. JP-A-11-257987). For example, in FIG. 13A, when the search is performed within each predetermined area on the departure point side and the destination side in a hierarchy level 1 having the detailed map data, and a boundary node SN11 that has a smallest search cost in the area on the departure point side and a boundary node DN11 that has a smallest search cost in the area on the destination side are searched, these boundary nodes are migrated to the corresponding nodes SN21 and DN21 in a hierarchy level 2, and then the route search is performed in the hierarchy level 2. When the route from the departure point side and the route from the destination side are connected in the overlapped part in the hierarchy level 2, a route P1 is set as the most appropriate route.